1. Числа Фибоначчи с кешированием (мемоизация).
Проблема обычной рекурсии fib(n-1) + fib(n-2) — экспоненциальная сложность. Решаем через словарь-кеш.
(Лекция 4)
cache = {}
def fib(n):
if n not in cache:
if n <= 2:
cache[n] = 1
else:
cache[n] = fib(n - 1) + fib(n - 2)
return cache[n]
# Или с использованием декоратора из стандартной библиотеки (как пример из лекции)
from functools import lru_cache # или @cache в Python 3.9+
@lru_cache(None)
def fib_decorated(n):
if n <= 2: return 1
return fib_decorated(n - 1) + fib_decorated(n - 2)
2. Палиндром максимальной длины вычеркиванием (Динамика по подотрезкам).
Дана строка. Найти самую длинную подстроку-палиндром, которую можно получить удалением лишних букв (не меняя порядок).
Пример: axyvxba -> xyvxb (не палиндром) -> ... -> abcba (нет) -> axyxa.
(Лекция 5)
# Используем срезы и рекурсию.
# Если края равны (s[0] == s[-1]) -> они входят в палиндром.
# Если нет -> пробуем отбросить левый или правый символ и ищем максимум.
def pal(s):
if len(s) <= 1:
return s
if s[0] == s[-1]:
return s[0] + pal(s[1:-1]) + s[-1]
else:
p1 = pal(s[:-1]) # Без последнего
p2 = pal(s[1:]) # Без первого
return p1 if len(p1) > len(p2) else p2
# Проблема: очень медленно без кеша.
# Решение с кешем (строка как ключ):
memo = {}
def pal_cached(s):
if s not in memo:
if len(s) <= 1:
memo[s] = s
elif s[0] == s[-1]:
memo[s] = s[0] + pal_cached(s[1:-1]) + s[-1]
else:
p1 = pal_cached(s[:-1])
p2 = pal_cached(s[1:])
memo[s] = p1 if len(p1) > len(p2) else p2
return memo[s]
3. Максимальный квадрат из нулей в матрице (Рекурсия).
Найти размер стороны максимального квадрата, состоящего только из 0.
(Лекция 5)
# Рекурсивная идея:
# Квадрат размера L в точке (x, y) состоит из нулей, если:
# 1. Сам он заполнен нулями (проверка).
# 2. ИЛИ это максимум из 4-х вложенных квадратов размера L-1
# (сдвинутых на 1 вправо, вниз и по диагонали).
# В лекции был подход с "разрезанием" матрицы на 4 части.
def square(M, y=0, x=0, L=None):
if L is None: L = len(M) # Начинаем с полного размера
# Проверка текущего квадрата (можно заменить на any/all)
is_zeros = all(M[i][j] == 0 for i in range(y, y+L) for j in range(x, x+L))
if is_zeros:
return L
else:
# Если не нули, ищем в 4-х подквадратах меньшего размера
# Внимание: это наивная рекурсия, очень медленная без кеша!
return max(
square(M, x, y, L-1), # Левый верхний (уменьшенный)
square(M, x+1, y, L-1), # Сдвиг вправо
square(M, x, y+1, L-1), # Сдвиг вниз
square(M, x+1, y+1, L-1) # Сдвиг по диагонали
)
4. Делители чисел на основе Решета Эратосфена (Список множеств).
Вместо простого вычеркивания сохраняем делители для каждого числа.
(Лекция 3)
n = 10
# L - список множеств. L[i] будет хранить простые делители числа i.
L = [set() for _ in range(n + 1)]
for i in range(2, n + 1):
if len(L[i]) == 0: # Если делителей нет, значит i - простое
# Добавляем i как делитель для всех кратных чисел (i, 2i, 3i...)
for j in range(i, n + 1, i):
L[j].add(i)
# Пример: L[6] будет {2, 3}, L[7] будет {7}
5. Сумма факториалов (Функциональный стиль).
Посчитать $\sum_{i=1}^n i!$ используя map, reduce.
(Лекция 6)
from functools import reduce
from operator import mul, add
# Факториал через reduce (свертка умножением)
# fact(5) -> 1*2*3*4*5
fact = lambda n: reduce(mul, range(1, n + 1))
n = 5
# 1. Генерируем числа: range(1, n+1)
# 2. Применяем fact к каждому: map(fact, ...)
# 3. Суммируем результат: reduce(add, ...) или sum(...)
result = sum(map(fact, range(1, n + 1)))
6. Сортировка составной коллекции по ключу.
Есть список кортежей (имя, возраст). Отсортировать по возрасту.
(Лекция 6)
data = [("Max", 20), ("Alex", 25), ("Kate", 18)]
# Используем параметр key и анонимную функцию lambda
sorted_data = sorted(data, key=lambda x: x[1]) # x[1] - возраст
# Результат: [("Kate", 18), ("Max", 20), ("Alex", 25)]
7. Декоратор функции вывода (Hello World).
Обернуть функцию так, чтобы она здоровалась и прощалась.
(Лекция 7)
def deco(func):
def wrapper(name):
print("Hello!") # Доп. действие ДО
func(name) # Вызов оригинала
print("Bye!") # Доп. действие ПОСЛЕ
return wrapper
@deco
def greet(name):
print(f"My name is {name}")
greet("Pavel")
# Вывод:
# Hello!
# My name is Pavel
# Bye!
8. Класс Вектор (Перегрузка операторов).
Реализовать сложение векторов и вычисление длины как свойства.
(Лекция 10)
class Vector(list): # Наследуемся от list для удобства хранения
def __init__(self, values):
super().__init__(values) # Инициализируем родительский list
def __add__(self, other):
# Поэлементное сложение: self[i] + other[i]
# Используем zip для параллельного прохода
new_values = [a + b for a, b in zip(self, other)]
return Vector(new_values)
@property
def length(self):
# Корень из суммы квадратов
return sum(x**2 for x in self) ** 0.5
v1 = Vector([1, 2])
v2 = Vector([3, 4])
v3 = v1 + v2 # Вызовет __add__: [4, 6]
print(v3.length) # Вызовет length
9. Генератор прогрессии.
Функция, которая выдает элементы геометрической прогрессии по одному (yield).
(Лекция 11)
def geom_progression(start, q, limit):
current = start
while current < limit:
yield current # "Выплевываем" значение и пауза
current *= q
# Использование
for x in geom_progression(1, 2, 20):
print(x) # 1, 2, 4, 8, 16
10. Нерекурсивный факториал в асинхронном режиме.
Запуск вычисления факториала как асинхронной задачи (Task).
(Лекция 14)
import asyncio
async def fact_async(n):
r = 1
for i in range(1, n + 1):
r *= i
await asyncio.sleep(0.01) # Имитация долгой работы, переключение контекста
return r
async def main():
# Создаем задачу
task = asyncio.create_task(fact_async(5))
print("Вычисляю...")
res = await task # Ждем результат
print(f"Факториал: {res}")
# Запуск: asyncio.run(main())